package solution;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    /**
     *28. 找出字符串中第一个匹配项的下标
     * https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/description/
     */
    public int strStr(String haystack, String needle) {
        int lenhay = haystack.length();
        int lenned = needle.length();

        if(haystack == null || needle == null) {
            return -1;
        }
        if(lenhay == 0 || lenned == 0) {
            return -1;
        }

        int i = 0;
        int j = 0;

        while(i < lenhay && j < lenned) {
            if(haystack.charAt(i) == needle.charAt(j)) {
                i++;
                j++;
            } else {
                i = i - j + 1;
                j = 0;
            }
        }

        if(j >= lenned) {
            return i - j;
        }
        return -1;
    }
    /**
     * 169. 多数元素
     * https://leetcode.cn/problems/majority-element/description/
     */
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }

    /**
     *121. 买卖股票的最佳时机
     * https://leetcode.cn/problems/best-time-to-buy-and-sell-stock/description/
     */
    public int maxProfit(int[] prices) {
        int minPrice = Integer.MAX_VALUE;
        int maxPrice = 0;
        for(int i = 0; i < prices.length; i++) {
            if(minPrice > prices[i]) {
                minPrice = prices[i];
            } else if(prices[i] - minPrice > maxPrice) {
                maxPrice = prices[i] - minPrice;
            }
        }
        return maxPrice;
    }

    /**
     * 119. 杨辉三角 II
     * https://leetcode.cn/problems/pascals-triangle-ii/description/
     * @param rowIndex
     * @return
     */
    public List<Integer> getRow(int rowIndex) {
        List<Integer> list1 = new ArrayList<>();
        List<List<Integer>> tmp = new ArrayList<List<Integer>>();

        //先构造好1 ~ rowIndex行的所有杨辉三角
        for(int i = 0; i < rowIndex + 1; i++) {
            List<Integer> list2 = new ArrayList<>();
            for(int j = 0; j <= i; j++) {
                if(j == 0 || i == j) {
                    list2.add(1);
                } else {
                    list2.add(tmp.get(i - 1).get(j - 1) + tmp.get(i - 1).get(j));
                }
            }
            tmp.add(list2);
        }
        return tmp.get(rowIndex);
    }
}